//! 简单的堆管理
//!

// ------------------------------------------------------------------------------------------
// 全局变量

use crate::mimalloc::link::{BlockLink, LIST};
use core::{alloc::Layout, ptr::null, sync::atomic::Ordering};

/// 堆的大小
pub(crate) const HEAP_SIZE: usize = 4 * (1 << 20); // 4 MB

unsafe extern "C" {
    fn sheap();
}

/// BlockLink这个结构体位于每一个分配的内存的开始位置，必须要正确的内存对齐。
pub(crate) static HEAP_STRUCT_SIZE: usize = size_of::<BlockLink>();

/// 出去对齐之后，真实可用的空间
pub(crate) static mut HEAP_REAL_AVAILABEL_SIZE: usize = 0;

/// 剩余多少自由空间，用来跟踪
pub(crate) static mut FREE_BYTES_REMAINNING: usize = HEAP_SIZE;

pub(crate) static HEAP_MINIMUM_BLOCK_SIZE: usize = HEAP_STRUCT_SIZE * 4;
// ------------------------------------------------------------------------------------------

/// 申请内存

pub(crate) unsafe fn malloc(want_size: usize) -> *mut u8 {
    unsafe {
        let mut ret = null::<u8>() as *mut u8;
        let mut layout =
            Layout::from_size_align_unchecked(want_size, align_of::<BlockLink>()).pad_to_align();

        while LIST.lock.compare_and_swap(false, true, Ordering::AcqRel) {
            continue;
        }

        // 检查初始化
        if LIST.end.is_null() {
            heap_init();
        }

        if layout.size() > 0 {
            layout =
                Layout::from_size_align_unchecked(layout.size() + HEAP_STRUCT_SIZE, layout.align());
        }

        if layout.size() > 0 && layout.size() < HEAP_REAL_AVAILABEL_SIZE {
            let mut prev_node = &mut LIST.first;
            let mut current_node = prev_node.next_free; // 第一个肯定有
            while (&*current_node).size < want_size && !(&*current_node).next_free.is_null() {
                prev_node = &mut *current_node;
                current_node = (&*current_node).next_free;
            }

            if current_node != LIST.end {
                // 找到了， 跳过BlockLink结构体
                ret = (prev_node.next_free as *mut u8).add(HEAP_STRUCT_SIZE) as *mut u8;

                // This block is being returned for use so must be taken out of
                // the list of free blocks.
                prev_node.next_free = (&*current_node).next_free;

                // if the block is larger than required it can be split into two.
                if (&*current_node).size - want_size > HEAP_MINIMUM_BLOCK_SIZE {
                    // this block is to be split into two. Create a new block following the number of bytes requested.

                    let new_block_link =
                        ((current_node as *mut u8).add(layout.size())) as *mut BlockLink;
                    (&mut *new_block_link).size = (&*current_node).size - layout.size();
                    (&mut *current_node).size = layout.size();

                    // inset the new block into the list of free blocks.
                    insert_block_into_free_list(new_block_link);
                }
                FREE_BYTES_REMAINNING -= layout.size();
            }
        }

        LIST.lock.store(false, Ordering::Release);
        ret
    }
}

/// 释放
pub(crate) unsafe fn free(p: *mut u8) {
    unsafe {
        while LIST.lock.compare_and_swap(false, true, Ordering::AcqRel) {
            continue;
        }

        let block_ptr = p.sub(HEAP_STRUCT_SIZE) as *const BlockLink;
        FREE_BYTES_REMAINNING += (&*block_ptr).size;
        insert_block_into_free_list(block_ptr as _);

        LIST.lock.store(false, Ordering::Release);
    }
}

pub(crate) unsafe fn insert_block_into_free_list(mut block_insert: *mut BlockLink) {
    unsafe {
        let start = &mut LIST.first;
        let mut iter = start;

        // Iterate through the list until a block is found that has a higher address
        // than the block being inserted.
        while iter.next_free < block_insert {
            iter = &mut *iter.next_free;
        }

        let puc = iter as *const BlockLink as *const u8;
        if puc.add(iter.size) == block_insert as *const u8 {
            iter.size += (&*block_insert).size;
            block_insert = iter as *const BlockLink as _;
        }

        let puc = block_insert as *const u8;

        if puc.add((&*block_insert).size) == iter.next_free as *const u8 {
            if iter.next_free != LIST.end {
                (&mut *block_insert).size += (&*iter.next_free).size;
                (&mut *block_insert).next_free = (&*iter.next_free).next_free;
            } else {
                (&mut *block_insert).next_free = LIST.end;
            }
        } else {
            (&mut *block_insert).next_free = iter.next_free;
        }

        if iter as *const BlockLink != block_insert {
            iter.next_free = block_insert;
        }
    }
}

/// 堆初始化
#[inline(always)]
unsafe fn heap_init() {
    unsafe {
        // 第一个节点并没有占用堆的空间，是一个全局变量，指示下一个节点的位置
        LIST.first.size = 0;
        LIST.first.next_free = as_ptr_mut_align(as_ptr_from_ref(sheap as usize));

        // end节点，用于标记空闲块列表的结束并插入在堆空间的末尾。
        let end: *mut u8 = as_ptr_from_ref(sheap as usize)
            .add(HEAP_SIZE)
            .sub(HEAP_STRUCT_SIZE);
        let align_end = align_down(end as _, align_of::<BlockLink>()) as *mut u8;
        LIST.end = align_end as *mut BlockLink;
        {
            let end = &mut *LIST.end;
            end.size = 0;
            end.next_free = null::<BlockLink>() as _;
        }

        // 真实可用的空间，是总的减去偏移的
        HEAP_REAL_AVAILABEL_SIZE = align_end.offset_from(as_ptr_from_ref(sheap as usize)) as usize
            - ((LIST.first.next_free as usize) - sheap as usize);

        // 创键第一个自由节点, 这个节点在HEAP上
        let bl = &mut *LIST.first.next_free;
        bl.size = HEAP_REAL_AVAILABEL_SIZE;
        bl.next_free = LIST.end;
        FREE_BYTES_REMAINNING = HEAP_REAL_AVAILABEL_SIZE;
    }
}

#[inline(always)]
fn as_ptr_mut_align<T>(ptr: *mut u8) -> *mut T {
    let align_value = align_of::<T>();
    if !ptr.is_aligned_to(align_value) {
        // 没有对齐
        return ((ptr as usize + align_value) & !(align_value - 1)) as *mut T;
    }
    ptr.cast()
}

// 向小的方向对齐
#[inline(always)]
fn align_down(ptr: *mut (), align: usize) -> *mut () {
    ((ptr as usize) & !(align - 1)) as *mut ()
}

#[inline(always)]
fn as_ptr_from_ref(heap: usize) -> *mut u8 {
    heap as *const u8 as *mut u8
}
